#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//using namespace std;
//
//const int N = 1e5 + 10;
//
//int l[N], r[N], n;
//
//void dfs(int u)
//{
//	if (!u)
//	{
//		return;
//	}
//
//	dfs(l[u]);
//	dfs(r[u]);
//	cout << u << " ";
//	
//}
//
//
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> l[i] >> r[i];
//	}
//
//	dfs(1);
//
//	return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//const int N = 1e5 + 10;
//
//int l[N], r[N];
//
//int n, root;
//
//void dfs(int root)
//{
//    if (root == 42)
//        return;
//    cout << (char)root;
//    dfs(l[root]);
//    dfs(r[root]);
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        string s;
//        cin >> s;
//        int index, left, right;
//        index = s[0];
//        left = s[1];
//        right = s[2];
//        if (i == 1)
//            root = index;
//        
//        l[index] = left;
//        r[index] = right;
//    }
//
//    dfs(root);
//
//    return 0;
//}


//#include<iostream>
//using namespace std;
//
//int n;
//const int N = 1e6 + 10;
//int l[N], r[N];
//
//int dfs(int u, int depth)
//{
//    if (u == 0)
//    {
//        return depth;
//    }
//
//    depth++;
//
//    return max(dfs(l[u], depth), dfs(r[u], depth));
//
//
//}
//
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> l[i] >> r[i];
//    }
//
//    int ret = dfs(1, 0);
//    cout << ret;
//
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//const int N = 1e5 + 10;
//
//int l[N], r[N];
//
//int n, root;
//
//void dfs(int root)
//{
//    if (root == 42)
//        return;
//    cout << (char)root;
//    dfs(l[root]);
//    dfs(r[root]);
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        string s;
//        cin >> s;
//        int index, left, right;
//        index = s[0];
//        left = s[1];
//        right = s[2];
//        if (i == 1)
//            root = index;
//
//        l[index] = left;
//        r[index] = right;
//    }
//
//    dfs(root);
//
//    return 0;
//}

//#include<iostream>
//using namespace std;
//
//const int N = 1e6 + 10;
//int n;
//int l[N], r[N];
//
//void dfs1(int u)
//{
//    if (u == 0)
//        return;
//    cout << u << " ";
//    dfs1(l[u]);
//    dfs1(r[u]);
//}
//
//void dfs2(int u)
//{
//    if (u == 0)
//        return;
//    dfs2(l[u]);
//    cout << u << " ";
//    dfs2(r[u]);
//}
//
//void dfs3(int u)
//{
//    if (u == 0)
//        return;
//    dfs3(l[u]);
//    dfs3(r[u]);
//    cout << u << " ";
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> l[i] >> r[i];
//    }
//
//    dfs1(1);
//    cout << endl;
//    dfs2(1);
//    cout << endl;
//    dfs3(1);
//    cout << endl;
//
//    return 0;
//}